package edu.bupt.c2linkedlist;

public class T01ReverseLinkedList {

    // 法-1：头插法
    // 重要点是，新建flag节点，且flag.next = null;
    public ListNode reverseList(ListNode head) {
        // 1-排除特殊情况 --从下面的情况看，也不需要做。
        if (null == head) return head;

        // 2-利用头插法
        ListNode flag = new ListNode(-1);
        flag.next = null;

        ListNode next = head;
        while(null != next){
            ListNode temp = next.next;
            next.next = flag.next;
            flag.next = next;
            next = temp;
        }
        return flag.next;
    }
    // 法-2：3个指针法
    public ListNode reverseList2(ListNode head){
        ListNode pre = null;
        ListNode index = head;
        while (null != index){
            ListNode temp = index.next;
            index.next = pre;
            pre = index;
            index = temp;
        }
        return pre;
    }
}
